#include <vector>
#include "./include/project.h"

using namespace std;


//文法的所有产生式数组
std::vector<formula> formulas;
//项目中的所有文法符号，包括终结符和非终结符
std::vector<sign> signs;
//根据文法生成的项目数组
std::vector<project> projects;


sign::sign(string s) {
  //如果在尖括号中，为非终结符
    if(s.length()>=3&&s[0]=='<'&&s[s.length()-1]=='>') {
      type = 1;
    } else {
      type = 0;
    }
    name = s;
}

void sign::add_to_first(string s) {
  bool existed = 0; int cur_len = first.size();
  for(int i=0;i<cur_len;i++) {
    if(s.compare(first[i])==0) {
      existed = 1;
      break;
    }
  }
  if(!existed) {
    first.push_back(s);
  }
}

void sign::add_to_follow(string s) {
  bool existed = 0; int cur_len = follow.size();
  for(int i=0;i<cur_len;i++) {
    if(s.compare(follow[i])==0) {
      existed = 1;
      break;
    }
  }
  if(!existed) {
    follow.push_back(s);
  }
}

bool sign::could_disappear() {
  std::vector<int> formula_id_list = get_formula_indexs_start_with_s(name);
  for(auto f_id:formula_id_list) {
    if(formulas[f_id].rights[0].name=="!")
      return true;
  }
  return false;
}

formula::formula(std::vector<string> v) {
  int len = v.size();
    if(len>0) {
      from = v[0];
      for(int i=1;i<len;i++) {
        rights.push_back(sign(v[i]));
      }
    }
}

sign item::get_cur_sign() {
  if(formulas[formula_id].rights.size()>p)
    return formulas[formula_id].rights[p];
  return sign("归约");
}

void project::add_item(const item & it) {
  for(auto i:items) {
    if(i.formula_id==it.formula_id&&i.p==it.p) {
      return;
    }
  }
  items.push_back(it);
}

void project::flash_ret_table() {
  for(auto i:items) {
    if(i.p==formulas[i.formula_id].rights.size() || formulas[i.formula_id].rights[0].name=="!") {
      //归约
      ret_table.push_back(project_ret(i.formula_id));
    }
  }
}

void project::e_closer() {
  for(int i=0;i<items.size();i++) {
    sign si = items[i].get_cur_sign();
    if(si.name.compare("归约")==0)
      continue;

    bool flag = 1;  int counter=0;
    while (flag) {
      flag = 0;
      if(si.type==1) {
        //找出所有以si为左部的产生式，并生成item加入到本project中
        std::vector<int> v = get_formula_indexs_start_with_s(si.name);
        for(auto i:v)
          add_item(item(i));
      }
    }
  }
}


/*
将一条文法读入文法数组中 如：
<常量说明部分> -- const <常量定义> <常量说明部分后缀> ;
*/
void create_forumla_into_formulas(string formula_s) {
  formula_s += ' ';
  int left=-1,right=-1;
  int len = formula_s.length();
  std::vector<string> strings;

  for(int i=0;i<len;i++) {
    if(formula_s[i]!=' ') {
      left = left==-1? i:left;
      right = right==-1? i:right+1;
    } else if(left!=-1&&right!=-1){
      //确保不把中间的分隔符当做文法符号
      if(formula_s.substr(left,right-left+1).compare("--")!=0) {
        strings.push_back(formula_s.substr(left,right-left+1));
        //把文法符号注册进signs中，！不是真正使用的文法符号
        if(formula_s.substr(left, right-left+1).compare("!")!=0) {
          add_sign_into_signs(formula_s.substr(left, right-left+1));
        }
      }
      left=right=-1;
    }
  }

  if(strings.size()!=0) {
    formulas.push_back(formula(strings));
  }
}

//从产生式数组中找出以sign_s为左部的产生式，返回在formulas中的索引数组
std::vector<int> get_formula_indexs_start_with_s(string sign_s) {
  std::vector<int> v;
  int len = formulas.size();
  for(int i=0;i<len;i++) {
    if(formulas[i].from==sign_s) {
      v.push_back(i);
    }
  }
  return v;
}


//在signs中加入新符号
void add_sign_into_signs(string sign_s) {
  for(auto sign:signs) {
    if(sign_s.compare(sign.name)==0) {
      return;
    }
  }
  signs.push_back(sign(sign_s));
}

//重排signs
void sort_signs() {
  int len = signs.size();
  for(int i=0;i<len;i++) {
    for(int j=0;j<len-i-1;j++) {
      if(signs[j]>signs[j+1]) {
        sign temp = signs[j];
        signs[j] = signs[j+1];
        signs[j+1] = temp;
      }
    }
  }
}

//根据sign.name获取sign在signs中的索引
int get_sign_index(string sign_s) {
  int len = signs.size();
  for(int i=0;i<len;i++) {
    if(sign_s==signs[i].name) {
      return i;
    }
  }
  return -1;
}


int add_project_into_projects(project &pro) {
  int len = projects.size();
  for(int i=0;i<len;i++) {
    if(pro==projects[i])
      return i;
  }
  pro.flash_ret_table();
  projects.push_back(pro);
  return len;
}

void set_goto(int pro_id) {
  //遍历符号表signs，如果对应某个终结符有状态，就新建状态并建立联系
  for(auto sign:signs) {
    project temp_pro;
    int len = projects[pro_id].items.size();
    for(int i=0;i<len;i++) {
      item it = projects[pro_id].items[i];
      if(sign.name.compare(it.get_cur_sign().name)==0) {
        if(formulas[it.formula_id].rights.size()>=it.p+1) {
          temp_pro.add_item(item(it.formula_id, it.p+1));
        }
      }
    }
    if(temp_pro.items.size()!=0) {
      temp_pro.e_closer();
      int id = add_project_into_projects(temp_pro);
      projects[pro_id].go_table.push_back(project_goto(sign.name, id));
    }
  }
}

void write_to_csv(string filename) {
  //制作csv表格
  ofstream data;
  data.open(filename, ios_base::ios_base::out | ios_base::trunc);
  if(!data.is_open()) {
    printf("打开文件失败\n");
  }

  //写入首行
  data<<',';
  for(auto i:signs)
    data<<'"'<<i.name<<'"'<<',';
  data<<endl;

  //逐行写入数据
  int *line_arr = new int[signs.size()];
  for(int i=0;i<projects.size();i++) {

    for(int _ = 0; _<signs.size();_++)
      line_arr[_] = 0;

    //处理移进
    for(auto _:projects[i].go_table) {
      //先找到keyword的索引下标
      int word_index = get_sign_index(_.word);
      line_arr[word_index] = _.project_id;
    }
    //处理归约
    if(projects[i].ret_table.size()>0) {
      //归约产生式的左部的follow集中的所有符号都要归约
      formula *fl = &(formulas[projects[i].ret_table[0].formula_id]);
      int word_index = get_sign_index(fl->from);
      for(auto _:signs[word_index].follow) {
        line_arr[get_sign_index(_)] += 10000*(projects[i].ret_table[0].formula_id+1);
      }
    }

    data<<"stat "<<i<<',';
    for(int _=0;_<signs.size();_++) {
      if(line_arr[_]==0) {
        data<<',';
      } else {
        if(line_arr[_]<10000) {
          //只有移进
          data<<"s "<<line_arr[_]<<',';
        } else if(line_arr[_]>=10000) {
          if(line_arr[_]%10000==0) {
            //只有归约,包括普通归约和acc
            if(line_arr[_]/10000==1) {
              data<<"acc"<<',';
            } else {
              data<<"r "<<line_arr[_]/10000-1<<',';
            }
          } else {
            //移进归约冲突
            data<<"s "<<line_arr[_]%10000<<" && r "<<line_arr[_]/10000-1<<',';
          }
        }

      }
    }
    data<<endl;
  }
  delete line_arr;
  data.close();
}

void display_table() {
  //打印项目集合
  for(int i=0;i<projects.size();i++) {
    cout<<"status "<<i<<endl;
    cout<<projects[i];
  }
  //打印符号状态
  for(int i=0;i<signs.size();i++) {
    cout<<signs[i];
  }
}

void reflash_formulas() {
  int l1 = formulas.size(),l2,l3 = signs.size();
  for(int i=0;i<l1;i++) {
    l2 = formulas[i].rights.size();
    for(int j=0;j<l2;j++) {
      for(int k=0;k<l3;k++) {
        if(formulas[i].rights[j].name.compare(signs[k].name)==0) {
          formulas[i].rights[j] = signs[k];
          break;
        }
      }
    }
  }
}

void init_signs_first() {
  int len = signs.size();
  for(int i=0;i<len;i++) {
    //寻找所有以signs[i]为左部的产生式
    std::vector<int> formula_id_list = get_formula_indexs_start_with_s(signs[i].name);
    //遍历每一条产生式
    for(int j = 0;j<formula_id_list.size();j++) {
      //获取当前产生式的右部
      std::vector<sign> cur_right = formulas[formula_id_list[j]].rights;
      //如果右部是终结符，加入signs[i]的first集中，如果是非终结符，将该非终结符的first并入sign[i]的first集中
      //如果非终结符可以消失，还要尝试继续处理下一个符号
      bool flag = 1; int counter = 0;//记录当前处理的符号在cur_right中的索引
      while(flag) {
        flag = 0;
        if(cur_right[counter].type==0) {
          if(cur_right[counter].name=="!")
            continue;
            signs[i].add_to_first(cur_right[counter].name);
        } else {
          //并入
          for(auto s:cur_right[counter].first) {
            signs[i].add_to_first(s);
          }
          //如果终结符可消失，还要继续处理后面的符号
          if(cur_right[counter].could_disappear()) {
            //如果该终结符后还有符号
            if(cur_right.size()>counter+1) {
              counter++;
              flag = 1;
            }
          }
        }
      }
    }
  }
  //刷新formulars中formual的right里的sign
  reflash_formulas();
}

void right_follow(sign &si,std::vector<sign> &v) {
  int len = v.size();
  for(int i=0;i<len-1;i++) {
    if(si.name==v[i].name) {
      //如果下一个有符号
      if(i<len-1) {
        //处理v[i+1]
        bool flag = 1; int counter = 1;
        while(flag) {
          flag = 0;
          if(v[i+counter].type==0) {
            si.add_to_follow(v[i+counter].name);
            //同步formulas中的sign
            v[i].add_to_follow(v[i+counter].name);
          } else {
            //把终结符的first集并到v[i]的follow集中
            for(auto s:v[i+counter].first) {
              si.add_to_follow(s);
              v[i].add_to_follow(s);
            }
            //如果终结符可消失，还要继续处理后面的符号
            if(v[i+counter].could_disappear()) {
              //后面还有符号
              if(i+counter+1<len) {
                counter++;
                flag = 1;
              }
            }
          }
        }
      }
    }
  }
}

void goal_keeper(formula & fl) {
  int len = fl.rights.size();
  for(int i = len - 1 ; i >= 0 ; i--) {
    //如果是终结符，不用做守门员处理
    if(fl.rights[i].type == 0)
      return;

    //守门员福利
    int sign_id1 = get_sign_index(fl.from);
    int sign_id2 = get_sign_index(fl.rights[i].name);
    for(auto s:signs[sign_id1].follow) {
      signs[sign_id2].add_to_follow(s);
    }

    //如果非终结符不可以消失，前面的符号不再有守门员福利
    if(!fl.rights[i].could_disappear()) {
      return;
    }
  }
}

void init_signs_follow() {
  //落井下石 文法的开始符号的follow集中加入结束符
  signs[get_sign_index("<S>")].add_to_follow("#");

  //右部follow
  int len = signs.size();
  for(int i=0;i<len;i++) {
    //遍历formulas寻找signs[i]的右部
    for(auto fl:formulas) {
      right_follow(signs[i],fl.rights);
    }
  }

  //守门员福利
  len = formulas.size();
  for(int i=0;i<len;i++) {
    //遍历formulas,处理每一条产生式的守门员福利
    goal_keeper(formulas[i]);
  }
}

void printf_projects() {
  for(auto pro:projects) {
    //输出分隔线
    cout<<"# # #"<<endl;
    //输出goto
    for(auto i:pro.go_table) {
      cout<<i.word<<" s "<<i.project_id<<endl;
    }
    //输出ret
    for(auto i:pro.ret_table) {
      int n = i.formula_id;
      string left = formulas[n].from;
      sign si = signs[get_sign_index(left)];
      for(auto j:si.follow) {
        if(i.formula_id!=0) {
          cout<<j<<" r "<<i.formula_id<<endl;
        } else {
          //acc
          cout<<j<<" acc "<<i.formula_id<<endl;
        }
      }
    }
  }
}
void write_to_txt(string filename) {
  ofstream out;
  out.open(filename);
  if(!out.is_open()) {
    cout<<"打开文件"<<filename<<"失败"<<endl;
    exit(0);
  }
  for(auto pro:projects) {
    //输出分隔线
    out<<"# # #"<<endl;
    //输出goto
    for(auto i:pro.go_table) {
      out<<i.word<<" s "<<i.project_id<<endl;
    }
    //输出ret
    for(auto i:pro.ret_table) {
      int n = i.formula_id;
      string left = formulas[n].from;
      sign si = signs[get_sign_index(left)];
      for(auto j:si.follow) {
        if(i.formula_id!=0) {
          out<<j<<" r "<<i.formula_id<<endl;
        } else {
          //acc
          out<<j<<" acc "<<i.formula_id<<endl;
        }
      }
    }
  }
  out.close();
}

int main(int argc,char ** argv) {
  //初始化产生式数组
  ifstream f;
  f.open("./files/新文法.txt");
  if(!f.is_open()) {
    printf("读取文法失败\n");
    exit(0);
  }
  string s;
  while(getline(f,s)) {
    create_forumla_into_formulas(s);
  }
  f.close();

  //重排signs
  sort_signs();
  //计算first集合和follow集合，需要多算几遍保证集合完整
  init_signs_first();
  init_signs_first();
  init_signs_first();
  init_signs_follow();
  init_signs_follow();
  init_signs_follow();


  //用第一条产生式初始化第一个状态
  project p;
  p.add_item(item(0));
  p.e_closer();
  p.flash_ret_table();
  projects.push_back(p);
  //生成所有状态
  for(int i=0;i<projects.size();i++)
    set_goto(i);


  //打印状态表
  display_table();
  //制作csv表格
  write_to_csv("./files/status_table.csv");
  //制作语法分析器可以直接读取的项目状态转移表
  write_to_txt("./files/status.txt");

  return 0;
}
